package 二叉树;
import java.util.*;
/**
 * 判断二叉树是否对称
 * 算法步骤：
 * 1. 从根节点的左右子树开始递归判断
 * 2. 判断左右子树是否镜像对称
 * 时间复杂度O(n)，空间复杂度O(h)，h为树的高度
 */
public class isSymmetric {
    /**
     * 二叉树节点类
     * 包含节点值、左子节点和右子节点
     */
    public static class TreeNode{
        int val;            // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点
        
        // 无参构造函数
        TreeNode(){}
        
        // 带值的构造函数
        TreeNode(int val){
            this.val = val;
        }
        
        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 判断二叉树是否对称的方法
     * 从根节点的左右子树开始判断
     * 
     * @param root 二叉树的根节点
     * @return 二叉树是否对称
     */
    public static boolean isSymmetricM(TreeNode root){
        // 空树是对称的
        if(root == null) return true;
        // 从根节点的左右子树开始判断
        return dfs(root.left, root.right);
    }

    /**
     * 递归判断两个子树是否镜像对称
     * 判断条件：
     * 1. 两个节点都为空，返回true
     * 2. 一个为空一个不为空，返回false
     * 3. 两个节点值不相等，返回false
     * 4. 递归判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点
     * 
     * @param left 左子树的根节点
     * @param right 右子树的根节点
     * @return 两个子树是否镜像对称
     */
    public static boolean dfs(TreeNode left, TreeNode right){
        // 两个节点都为空，返回true
        if(left == null && right == null) return true;
        // 一个为空一个不为空，返回false
        if(left == null || right == null) return false;
        // 两个节点值不相等，返回false
        if(left.val != right.val) return false;
        // 递归判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

    /**
     * 使用迭代方法判断两个子树是否镜像对称
     * 使用队列进行层序遍历，每次取出两个节点进行比较
     * 判断条件：
     * 1. 两个节点都为空，继续比较下一对节点
     * 2. 一个为空一个不为空，返回false
     * 3. 两个节点值不相等，返回false
     * 4. 将左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点加入队列
     * 
     * @param left 左子树的根节点
     * @param right 右子树的根节点
     * @return 两个子树是否镜像对称
     */
    public static boolean iteration(TreeNode left, TreeNode right){
        // 创建队列，用于存储待比较的节点对
        Queue<TreeNode> queue = new LinkedList<>();
        // 将左右子树的根节点加入队列
        queue.offer(left);
        queue.offer(right);
        
        // 当队列不为空时，继续比较
        while(!queue.isEmpty()){
            // 取出两个节点进行比较
            left = queue.poll();
            right = queue.poll();
            
            // 两个节点都为空，继续比较下一对节点
            if(left == null && right == null) continue;
            // 一个为空一个不为空，返回false
            if(left == null || right == null) return false;
            // 两个节点值不相等，返回false
            if(left.val != right.val) return false;

            // 将左子树的左节点和右子树的右节点加入队列
            queue.offer(left.left);
            queue.offer(right.right);

            // 将左子树的右节点和右子树的左节点加入队列
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;  // 所有节点对都满足对称条件，返回true
    }

    /**
     * 根据层序遍历的字符串数组构建二叉树
     * 使用队列进行层序遍历构建
     * 
     * @param nodes 层序遍历的节点值数组，"null"表示空节点
     * @return 构建好的二叉树根节点
     */
    public static TreeNode buildTree(String[] nodes){
        // 处理特殊情况：空数组或根节点为空
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null")){
            return null;
        }
        
        // 使用队列进行层序遍历构建
        Queue<TreeNode> queue = new LinkedList<>();
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        int index = 1;  // 当前处理的节点在数组中的索引
        
        // 层序遍历构建二叉树
        while(!queue.isEmpty() && index < nodes.length){
            TreeNode cur = queue.poll();  // 取出当前节点
            
            // 处理左子节点
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.left);
            }
            index++;
            
            // 处理右子节点
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用空格分隔，表示二叉树的层序遍历，"null"表示空节点
     * 例如：1 2 2 3 4 4 3 表示一个对称的二叉树
     *      1 2 2 null 3 null 3 表示一个不对称的二叉树
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取二叉树节点值
        String[] nodes = sc.nextLine().split(" ");
        
        // 构建二叉树并判断是否对称
        TreeNode root = buildTree(nodes);
        boolean result = isSymmetricM(root);
        System.out.println(result);
        sc.close();
    }
}
